package dateStructure;

import sun.misc.Queue;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.ConcurrentLinkedQueue;

public class binaryTree1 {
//    //询问法
//    public static void main(String arg[]){
//        TNode MyT=new TNode();
//        createTree(MyT);
//    }
//    private static class TNode{
//        TNode lchild;
//        TNode rchild;
//        String data;
//    }
//    public static void createTree(TNode T){
//        Scanner scanner =new Scanner(System.in);
//        System.out.print("请输入节点的信息：");
//        T=new TNode();
//        T.data=scanner.nextLine();
//        String check;
//        System.out.print("节点"+T.data+"是否有左节点(Y/N)：");
//        check=scanner.nextLine();
//        if(check.equals("Y")){
//            createTree(T.lchild);
//        }
//        else{
//            T.lchild=null;
//        }
//        System.out.print("节点"+T.data+"是否有右节点(Y/N)：");
//        check=scanner.nextLine();
//        if(check.equals("Y")){
//            createTree(T.rchild);
//        }
//        else{T.rchild=null;}
//    }
}

class binaryTree2 {
//    public static void main(String arg[]) {
//        TNode MyT = new TNode();
//        MyT=createTree(MyT);
//        preOrder(MyT);
//        System.out.println();
//        inOrder(MyT);
//        System.out.println();
//        postOrder(MyT);
//    }
//    private static class TNode {
//        TNode lchild;
//        TNode rchild;
//        String data;
//    }
//    public static TNode createTree(TNode T) {
//        Scanner scanner = new Scanner(System.in);
//        String point;
//        System.out.print("请输入节点的名称(”#“代表空节点)：");
//        T = new TNode();
//        point = scanner.nextLine();
//        if (point.equals("#")) {
//            T = null;
//        }
//        else {
//            T.data = point;
//            T.lchild = createTree(T.lchild);
//            T.rchild = createTree(T.rchild);
//        }
//        return T;
//    }
//    public static void preOrder(TNode T) {
//        if (T != null) {
//            System.out.print(T.data + " ");
//            preOrder(T.lchild);
//            preOrder(T.rchild);
//        }
//    }
//
//    public static void inOrder(TNode T) {
//        if (T != null) {
//            inOrder(T.lchild);
//            System.out.print(T.data + " ");
//            inOrder(T.rchild);
//        }
//    }
//
//    public static void postOrder(TNode T) {
//        if (T != null) {
//            postOrder(T.lchild);
//            postOrder(T.rchild);
//            System.out.print(T.data + " ");
//        }
//    }
}

class   binaryTree3 {
    //ABD##E##CF#G###
//    public static void main(String arg[]) {
//        TNode MyT = new TNode();
//        MyT = createTree(MyT);
//        System.out.print("先序遍历为：");
//        preOrder(MyT);
//        System.out.println();
//
//        System.out.print("中序遍历为：");
//        inOrder(MyT);
//        System.out.println();
//
//        System.out.print("后序遍历为：");
//        postOrder(MyT);
//        System.out.println();
//
//        System.out.print("层序遍历为：");
//        levelOrder(MyT);
//        System.out.println();
//    }
//
//    private static class TNode {
//        TNode lchild;
//        TNode rchild;
//        String data;
//    }
//
//    public static TNode createTree(TNode T) {
//        Scanner scanner = new Scanner(System.in);
//        String point;
//        System.out.print("请输入节点的信息（“#”代表节点为空）：");
//        point = scanner.nextLine();
//        if (point.equals("#")) {
//            T = null;
//        } else {
//            T = new TNode();
//            T.data = point;
//            T.lchild = createTree(T.lchild);
//            T.rchild = createTree(T.rchild);
//        }
//        return T;
//    }
//
//    public static void preOrder(TNode T) {
//        if (T != null) {
//            System.out.print(T.data + " ");
//            preOrder(T.lchild);
//            preOrder(T.rchild);
//        }
//    }//ABD##E##CF#G###
//
//    public static void inOrder(TNode T) {
//        if (T != null) {
//            preOrder(T.lchild);
//            System.out.print(T.data + " ");
//            preOrder(T.rchild);
//        }
//    }
//
//    public static void postOrder(TNode T) {
//        if (T != null) {
//            preOrder(T.lchild);
//            preOrder(T.rchild);
//            System.out.print(T.data + " ");
//        }
//    }
//
//    public static boolean levelOrder(TNode T) {
//        if (T != null) {
//            LinkedList<TNode> q=new LinkedList<>();
//            TNode t;
//            q.add(T);
//            while (!q.isEmpty()){
//                t=q.pop();
//                System.out.print(t.data+" ");
//                if(t.lchild!=null){
//                    q.add(t.lchild);
//                }
//                if(t.rchild!=null){
//                    q.add(t.rchild);
//                }
//            }
//            return true;
//        }
//        return false;
//    }
    //线索二叉树中序
//    private static TNode pre;
//
//    private static void inThread(TNode t) {
//        pre = new TNode();
//        if (t != null) {
//            createinTread(t);
//            pre.rchild = null;
//            pre.rtag = 1;
//        }
//    }
//
//    private static void createinTread(TNode t) {
//        if (t != null) {
//            createinTread(t.lchild);
//            if (t.lchild == null) {
//                t.lchild = pre;
//                t.ltag = 1;
//            } else {
//                t.ltag = 0;
//            }
//            if (pre != null) {
//                if (pre.rchild == null) {
//                    pre.rchild = t;
//                    pre.rtag = 1;
//                } else {
//                    pre.rtag = 0;
//                }
//            }
//            pre = t;
//            createinTread(t.rchild);
//        }
//    }
//
//    private static void inthreadOrder(TNode t) {
//        TNode p = t;
//        while (p != null) {
//            while (p.ltag == 0) {
//                p = p.lchild;
//            }
//            System.out.print(p.value + " ");
//            while (p.rchild != null && p.rtag ==1) {
//                p = p.rchild;
//                System.out.print(p.value + " ");
//
//            }
//            p = p.rchild;
//        }
//    }
}

class binaryTree4 {
    /**
     * NULL A L
     * A B L
     * A C R
     * B D R
     * C E L
     * C F R
     * D G L
     * F H L
     * NULL NULL L
     *
     * ABD##E##CF#G###
     */
    //计算二叉树的叶子节点和节点数
    public static void main(String arg[]) {
        TNode MyT = new TNode();
        MyT = pre_mid_createTree("ABDECFG","DBEAFGC",7);
//        preOrder(MyT);
//        System.out.println();
//        inOrder(MyT);
//        System.out.println();
        System.out.print("后序遍历为：");
        postOrder(MyT);
        System.out.println();
        System.out.println("叶子节点数为：" + leaveNumber(MyT) + "\n" + "节点数为：" + pointNumber(MyT));
    }

    private static class TNode {
        TNode lchild, rchild;
//        String data;
        char data;
    }
    private static TNode pre_mid_createTree(String pre,String mid,int len){
        if(len==0){
            return null;
        }
        char t=pre.charAt(0);//is point
        TNode T=new TNode();
        T.data=t;//***关键是找到根
        int index=0;
        while (mid.charAt(index)!=t){
            index++;//finding the point
        }
        //（先序：根左右），（中序：左根右）
        T.lchild=pre_mid_createTree(pre.substring(1),mid.substring(0),index);//所以左子树是先序在格后面，中序在最前面
        T.rchild=pre_mid_createTree(pre.substring(index+1),mid.substring(index+1),len-index-1);//所以右子树一定在后面
        return T;
    }
//    private static TNode post_mid_createTree(String post,String mid,int len){
//        if(len==0){
//            return null;
//        }
//        TNode T;
//        char t=post.charAt(len-1);
//        int index=0;
//        while (mid.charAt(index)!=t){
//            index++;
//        }
//        T=new TNode();
//        T.data=t;
//        T.lchild=post_mid_createTree(post.substring(0),mid,index);
//        T.rchild=post_mid_createTree(post.substring(index),mid.substring(index+1),len-index-1);
//        return T;
//    }
//    private static TNode createTree(TNode T) {
//        Scanner scanner = new Scanner(System.in);
//        LinkedList<TNode> q = new LinkedList<>();
//        String a, b, c;
//        TNode p, node;
//        a = scanner.next();
//        b = scanner.next();
//        c = scanner.next();
//        if (a.equals("NULL") && !b.equals("NULL")) {
//            T = new TNode();
//            T.data = b;
//            T.lchild = T.rchild = null;
//            q.add(T);
//        }
//        a = scanner.next();
//        b = scanner.next();
//        c = scanner.next();
//        while (!q.isEmpty() && !a.equals("NULL") && !b.equals("NULL")) {
//            p = q.pop();
//            while (a.equals(p.data)) {//最多循环两次
//                node = new TNode();
//                node.data = b;
//                node.lchild = node.rchild = null;
//                if (c.equals("L")) {
//                    p.lchild = node;
//                    System.out.println(node.data + " is " + p.data + " lchild");
//                } else {
//                    p.rchild = node;
//                    System.out.println(node.data + " is " + p.data + " rchild");
//                }
//                q.add(node);
//                a = scanner.next();
//                b = scanner.next();
//                c = scanner.next();
//            }
//        }
//        return T;
//    }
    public static void preOrder(TNode T) {
        if (T != null) {
            System.out.print(T.data + " ");
            preOrder(T.lchild);
            preOrder(T.rchild);
        }
    }

    public static void inOrder(TNode T) {
        if (T != null) {
            inOrder(T.lchild);
            System.out.print(T.data + " ");
            inOrder(T.rchild);
        }
    }

    public static void postOrder(TNode T) {
        if (T != null) {
            postOrder(T.lchild);
            postOrder(T.rchild);
            System.out.print(T.data + " ");
        }
    }

    private static int leaveNumber(TNode T) {
        if (T == null) {
            return 0;
        }
        if (T.lchild == null && T.rchild == null) {
            return 1;
        } else {
            return leaveNumber(T.lchild) + leaveNumber(T.rchild);
        }
    }

    public static int pointNumber(TNode T) {
        if (T == null) {
            return 0;
        } else {
            return pointNumber(T.lchild) + pointNumber(T.rchild) + 1;
        }
    }
    public static int depthTree(TNode T){
        if(T==null){
            return 0;
        }
        int m=depthTree(T.lchild);
        int n=depthTree(T.rchild);
        if(m>n){
            return m+1;
        }
        return n+1;
    }
}
